// https://www.lintcode.com/problem/tower-of-hanoi/description

class Solution {
public:
    /**
     * @param n: the number of disks
     * @return: the order of moves
     */
    // vector<string> help(string start, string mid, string end, int n)
    // {
    //     vector<string> result;
    //     if (n == 1) 
    //     { 
    //         result.push_back("from " + start + " to " + end);
    //         return result;
    //     }
    //     vector<string> atob = help(start, end, mid, n - 1);
    //     vector<string> atoc = help(start, mid, end, 1);
    //     vector<string> btoc = help(mid, start, end, n - 1);
    //     result = atob;
    //     result.insert(result.end(), atoc.begin(), atoc.end());
    //     result.insert(result.end(), btoc.begin(), btoc.end());
    //     return result;
    // }
   
    // vector<string> towerOfHanoi(int n) {
    //     vector<string> result = help("A", "B", "C", n);
    //     return result;
    // }
    
    // 其实就是一个dfs
    void help(vector<string>& result, string start, string mid, string end, int n)
    {
        if (n < 1) return;
        help(result, start, end, mid, n - 1);
        result.push_back("from " + start + " to " + end);
        help(result, mid, start, end, n - 1);
    }
    
    vector<string> towerOfHanoi(int n) {
        vector<string> result;
        help(result, "A", "B", "C", n);
        return result;
    }
};